МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ДОСЛІДЖЕННЯ ШИФРІВ ПІДСТАНОВКИ.
МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 1
З ДИСЦИПЛІНИ “КРИПТОГРАФІЧНІ СИСТЕМИ ТА ПРОТОКОЛИ”
для студентів базового напряму
6.170101 “Безпека інформаційних і комунікаційних систем”
Затверджено на засiданнi кафедри
“Безпека інформаційних технологій”,
протокол № від 2012 р.
Львів – 2012
Дослідження шифрів підстановки: Методичні вказівки до лабораторної роботи №1 з дисципліни “Криптографічні системи та протоколи” для студентів базового напряму 6.170101 “Безпека інформаційних і комунікаційних систем” /Укл.: А.Е.Лагун, А.В.Петришин - Львів: НУЛП 2012. - 00 с.
Укладачі: А.Е.Лагун, к.т.н., доцент
А.В.Петришин, асистент
Відповідальний за випуск:
Л.В. Мороз, к.т.н., доцент.
Рецензент: В.М.Максимович, д.т.н., професор.
Мета роботи - вивчити основні характеристики шифрів підстановки і навчитися розробляти програмне забезпечення для реалізації алгоритмів шифрування з використанням шифрів підстановки на комп’ютері.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
1.1. МОНОАЛФАВІТНІ ПІДСТАНОВКИ
Нехай Zm = {z1, z2,…, zm}- алфавіт відкритого та шифрованого текстів.
Підстановкою на алфавіті Zm називається взаємно-однозначне відображення .
Інакше кажучи, будь-яка перестановка елементів Zm визначає підстановку на Zm . Множина підстановок на Zm утворює групу відносно операції множення. Одиницею цієї групи є тотожна підстановка; для кожної підстановки π існує обернена підстановка π -1 : π π -1 = 1. Ця група називається симетричною і позначається SYM(Zm). Кількість всіх підстановок на Zm дорівнює m!
Якщо задана підстановка π на Zm , то можна згідно з нею букві відкритого тексту співставити букву шифротексту. Але криптографічне перетворення повинно задавати правило шифрування тексту будь-якої довжини n.
Позначимо - множину n-грам над алфавітом Zm.
Криптографічним перетворенням Т називається сімейство перетворень , де .
Підстановка (як криптосистема) – це криптографічне перетворення Т, де . Тобто, при шифруванні шифром підстановки тексту довжини n перша буква шифротексту одержується з першої букви відкритого тексту за допомогою π1, друга – за допомогою π2 , ..., остання – за допомогою πn. Таким чином, криптографічне перетворення Т задається ключем - нескінченною послідовністю підстановок. Букви при підстановці шифруються незалежно одна від одної і кожна, взагалі кажучи, є своєю підстановкою.
Підстановка називається моноалфавітною, якщо πі = π , і=1,2,... (тобто всі букви шифруються тією ж самою підстановкою). Якщо ж у послідовності не всі підстановки однакові, то таке криптографічне перетворення називається поліалфавітною підстановкою.
Моноалфавітну підстановку ще називають шифром простої заміни.
При моноалфавітній підстановці одна й та ж сама буква алфавіту, що зустрічається у відкритому тексті, шифрується тією ж самою буквою шифротексту незалежно від її місця у тексті. Наприклад, якщо підстановка π переводить букву „а” в букву „м”, то де б не зустрілась буква „а” у відкритому тексті, вона буде зашифрована як „м”. У разі ж поліалфавітної підстановки одна й та сама буква алфавіту може шифруватись по-різному в залежності від її місця у відкритому тексті.
1.1.1. Шифр Цезаря
Найпростіша моноалфавітна підстановка – це шифр Цезаря. Ототожнимо букви алфавіту Zm з цифрами від 0 до m-1 і позначимо x – довільну букву відкритого тексту, а y – відповідну букву шифротексту. Тоді в шифрі Цезаря , де - ключ (Цезар використовував ключ b=3). В цьому випадку підстановка на алфавіті є циклічним зсувом алфавіту на позицій вправо.
Для того, щоб знайти ключ, маючи лише шифротекст, знайдемо y* - букву, що найчастіше зустрічається у шифротексті. Нехай x* - буква алфавіту, що має найбільшу частоту у мові, якою написаний відкритий текст. Тоді, якщо текст достатньо довгий, щоб у ньому проявилися закономірності мови, найвірогідніше, що x* зашифровано y*. Отже, маємо , звідки ключ ...
